package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class P448FindAllNumbersDisappearedInAnArray {
    public static void main(String[] args) {

        Solution solution = new P448FindAllNumbersDisappearedInAnArray().new Solution();
        System.out.println(solution.findDisappearedNumbers(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> findDisappearedNumbers(int[] nums) {
            int n = nums.length;
            for (int num : nums) {
                int x = (num - 1) % n;
                nums[x] += n;
            }
            List<Integer> ret = new ArrayList<Integer>();
            for (int i = 0; i < n; i++) {
                if (nums[i] <= n) {
                    ret.add(i + 1);
                }
            }
            return ret;
        }


        public List<Integer> findDisappearedNumbersMy(int[] nums) {
            List<Integer> list = new ArrayList<>();
            int[] arr = new int[nums.length];
            for (int num : nums) {
                arr[num - 1] = -1;
            }
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] != -1) {
                    list.add(i + 1);
                }
            }
            return list;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}